from glLibLocals import *
from glLibMath import *
class glLibPathFinder:
    def __init__(self,data=None):
        self.connections = {}
        if data == None:
            pass
        elif type(data) == type(""):
            file = open(data,"r")
            data = file.readlines()
            for line in data:
                line = line.strip()
                if line == "" or line.startswith("#"): continue
                node_name,line = line.split(":")
                node_name = node_name.strip()
                line = line.split("|")
                line = [a.strip() for a in line]
                connection_list = []
                for connection in line:
                    name,cost = connection.split(" ")
                    if cost.startswith("s"):
                        cost = float(cost[1:])**0.5
                    elif cost == "inf":
                        cost = "inf"
                    try: cost = float(cost)
                    except: raise glLibError("Cost value "+str(cost)+" not recognized!")
                    if cost < 0.0:
                        raise glLibError("Cost value "+str(cost)+" must be positive or zero!")
                        
                    connection_list.append([name,cost])
                self.connections[node_name] = connection_list
        elif hasattr(data,"raw_vertices"):
            for vertex in data.raw_vertices:
                self.connections["Node__"+str(tuple(vertex))] = []
            for edge in data.raw_polygons:
                n1 = str(tuple(edge[0]))
                n2 = str(tuple(edge[1]))
                dist = length(vec_subt(*edge))
                self.connections["Node__"+n1].append(["Node__"+n2,dist])
                self.connections["Node__"+n2].append(["Node__"+n1,dist])
                        
    def glLibInternal_path_length(self,path_names):
        distance = 0.0
        for index in xrange(0,len(path_names)-1,1):
            for conn in self.connections[path_names[index]]:
                if conn[0] == path_names[index+1]:
                    if conn[1] == "inf": return None
                    distance += conn[1]
                    break
        return distance
    def set_all_distances(self,new_distance):
        for node in self.connections.values():
            for conn in node:
                conn[1] = new_distance
    def find_path(self,from_name,to_name):
        #http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm
        node_names = self.connections.keys()
        distance_register = {}
        previous_node_register = {}
        for node_name in node_names: #Initializations
            distance_register[node_name] = "inf" #Unknown distance function from source to v
            previous_node_register[node_name] = None #Previous node in optimal path from source
        distance_register[from_name] = 0.0 #Distance from source to source
        Q = node_names
        #All nodes in the graph are unoptimized - thus are in Q
        while len(Q) != 0: #The main loop
##            distances = []
##            for key in Q:
##                distances.append([distance_register[key],key])
            distances = [[distance_register[key],key] for key in Q]
            distances.sort() #strings get placed last, so "inf" goes last too
            u = distances[0][1]
            if distance_register[u] == "inf":
                return False #all remaining vertices are inaccessible from source
            if u == to_name:
                S = []
                while previous_node_register[u] != None:
                    S = [u]+S
                    u = previous_node_register[u]
                S = [from_name]+S
                if len(S) == 1:
                    return True
                return S,self.glLibInternal_path_length(S)
            Q.remove(u)
            for node_name,distance_to in self.connections[u]:
                if distance_to == "inf": continue
                alt = distance_register[u] + distance_to
                if alt < distance_register[node_name]: #Relax (u,v,a)
                    distance_register[node_name] = alt
                    previous_node_register[node_name] = u
    def save_network(self,name,write_inf=False):
        string = """#This is a network file automatically generated by glLib.
#Use "#" to specify comments.  Nodes are listed by name.
#Each line specifies a single node and its connections to
#other nodes and their distances.  The node is the first
#name, then a ":" character, then, connections are
#specified by new node names and distances to them along
#a direct route (if a node is not directly connected to
#another node, then it should not be listed under the
#node's connections.  The connections to individual nodes
#are separated by a "|" symbol.

"""
        node_strings = []
        for nodename in self.connections.keys():
            node_string = nodename+":  "
            connections = self.connections[nodename]
            connection_strings = []
            for connection in connections:
                if connection[1] == "inf":
                    dist = "inf"
                    if write_inf:
                        connection_strings.append(" | "+connection[0]+" "+dist)
                else:
                    dist = float(connection[1])
                    if float(int(connection[1])) == connection[1]:
                        dist = int(connection[1])
                    for x in xrange(2,10):
                        if dist == float(x)**0.5:
                            dist = "s"+str(x)
                    connection_strings.append(" | "+connection[0]+" "+str(dist))
            connection_strings.sort()
            connection_strings[0] = connection_strings[0][3:]
            for connection_string in connection_strings:
                node_string += connection_string
            node_string += "\n"
            node_strings.append(node_string)
        node_strings.sort()
        for node_string in node_strings:
            string += node_string
        file = open(name,"w")
        file.write(string)
        file.close()
